package com.leetcode.algorithm.common;

/**
 * Quick Union 的「并查集」实现代码
 * +路径压缩
 * 
 * @author jie.deng
 *
 */
public class UnionFind03 {
	// 实际存储的是parent,经过路径压缩后存储的是root
	int roots[];

	public UnionFind03(int size) {
		roots = new int[size];
		for (int i = 0; i < size; i++) {
			roots[i] = i;
		}
	}

	private int findRoot(int x) {
		int root = roots[x];
		while (x != root) {
			root = roots[root];
		}
		// 从x到root的路径上的所有节点的parent赋值为root
		while (root != x) {
			int tmp = roots[x];
			roots[x] = root;
			x = tmp;
		}
		return root;
	}

	public void union(int x, int y) {
		int rootX = findRoot(x);
		int rootY = findRoot(y);
		if (rootX != rootY) {
			roots[rootY] = rootX;
		}
	};

	public boolean isConnected(int x, int y) {
		return findRoot(x) == findRoot(y);
	}
}